package com.sicheng.lc.周赛.分类.栈.单调栈or单调队列;

import java.util.ArrayDeque;
import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/15 22:57
 */
public class 柱状图中最大的矩形 {
    //https://leetcode.cn/problems/largest-rectangle-in-histogram/
    static int N = (int) 1e5;
    static int[] left = new int[N];
    static int[] right = new int[N];
    static ArrayDeque<Integer> deque = new ArrayDeque<>((int) 1e4);

    {
        deque.clear();
        Arrays.fill(left, 0);
        Arrays.fill(right, N - 1);
    }

    public int largestRectangleArea(int[] heights) {
        for (int i = 0; i < heights.length; i++) {
            while (!deque.isEmpty() && heights[i] <= heights[deque.peek()])
                deque.pop();
            if (!deque.isEmpty())
                left[i] = deque.peek() + 1;
            deque.push(i);
        }
        deque.clear();
        for (int i = heights.length - 1; i >= 0; i--) {
            while (!deque.isEmpty() && heights[i] < heights[deque.peek()])
                deque.pop();
            if (!deque.isEmpty())
                right[i] = deque.peek() - 1;
            deque.push(i);
        }

        int res = 0;
        for (int i = 0; i < heights.length; i++) {
            int L = left[i], R = right[i];
            res = Math.max(res, (R - L + 1) * heights[i]);
        }
        return res;
    }
}
